The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the stochastic block model or planted partition problem, where a phase transition takes place in the detection of the planted partition by changing the signal-to-noise ratio. Optimal algorithms for the detection exist which are based on spectral methods, but we show these are extremely sensible to slight modification in the generative model. Recently Javanmard, Montanari and Ricci-Tersenghi [1] have used statistical physics arguments, and numerical simulations to show that finding communities in the stochastic block model via semidefinite programming is quasi optimal. Further, the resulting semidefinite relaxation can be solved efficiently, and is very robust with respect to changes in the generative model. In this paper we study in detail several practical aspects of this new algorithm based on semidefinite programming for the detection of the planted partition. The algorithm turns out to be very fast, allowing the solution of problems with O(105) variables in few second on a laptop computer.

Performance of a community detection algorithm based on semidefinite programming / RICCI TERSENGHI, Federico; Javanmard, Adel; Montanari, Andrea. - In: JOURNAL OF PHYSICS. CONFERENCE SERIES. - ISSN 1742-6588. - ELETTRONICO. - 699:(2016), p. 012015. [10.1088/1742-6596/699/1/012015]

Performance of a community detection algorithm based on semidefinite programming

RICCI TERSENGHI, Federico;
2016

Abstract

The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the stochastic block model or planted partition problem, where a phase transition takes place in the detection of the planted partition by changing the signal-to-noise ratio. Optimal algorithms for the detection exist which are based on spectral methods, but we show these are extremely sensible to slight modification in the generative model. Recently Javanmard, Montanari and Ricci-Tersenghi [1] have used statistical physics arguments, and numerical simulations to show that finding communities in the stochastic block model via semidefinite programming is quasi optimal. Further, the resulting semidefinite relaxation can be solved efficiently, and is very robust with respect to changes in the generative model. In this paper we study in detail several practical aspects of this new algorithm based on semidefinite programming for the detection of the planted partition. The algorithm turns out to be very fast, allowing the solution of problems with O(105) variables in few second on a laptop computer.
2016
.
01 Pubblicazione su rivista::01a Articolo in rivista
Performance of a community detection algorithm based on semidefinite programming / RICCI TERSENGHI, Federico; Javanmard, Adel; Montanari, Andrea. - In: JOURNAL OF PHYSICS. CONFERENCE SERIES. - ISSN 1742-6588. - ELETTRONICO. - 699:(2016), p. 012015. [10.1088/1742-6596/699/1/012015]
File allegati a questo prodotto
File Dimensione Formato  
Ricci-Tersenghi_Performance of a community_2016.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 524.34 kB
Formato Adobe PDF
524.34 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/868048
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact